Search results for "Static routing"
showing 10 items of 29 documents
Addressing Manufacturing Challenges with Cost-Efficient Fault Tolerant Routing
2010
The high-performance computing domain is enriching with the inclusion of Networks-on-chip (NoCs) as a key component of many-core (CMPs or MPSoCs) architectures. NoCs face the communication scalability challenge while meeting tight power, area and latency constraints. Designers must address new challenges that were not present before. Defective components, the enhancement of application-level parallelism or power-aware techniques may break topology regularity, thus, efficient routing becomes a challenge.In this paper, uLBDR (Universal Logic-Based Distributed Routing) is proposed as an efficient logic-based mechanism that adapts to any irregular topology derived from 2D meshes, being an alter…
The mixed capacitated general routing problem with turn penalties
2011
In this paper we deal with the mixed capacitated general routing problem with turn penalties. This problem generalizes many important arc and node routing problems, and it takes into account turn penalties and forbidden turns, which are crucial in many real-life applications, such as mail delivery, waste collection and street maintenance operations. Through a polynomial transformation of the considered problem into a Generalized Vehicle routing problem, we suggest a new approach for solving this new problem by transforming it into an Asymmetric Capacitated Vehicle routing problem. In this way, we can solve the new problem both optimally and heuristically using existing algorithms. A powerfu…
A Branch-and-Cut method for the Capacitated Location-Routing Problem
2011
International audience; Recent researches in the design of logistic networks have shown that the overall distribution cost may be excessive if routing decisions are ignored when locating depots. The Location-Routing Problem (LRP) overcomes this drawback by simultaneously tackling location and routing decisions. The aim of this paper is to propose an exact approach based on a Branch-and-Cut algorithm for solving the LRP with capacity constraints on depots and vehicles. The proposed method is based on a zero-one linear model strengthened by new families of valid inequalities. The computational evaluation on three sets of instances (34 instances in total), with 5–10 potential depots and 20–88 …
TBRA: A scalable routing algorithm in highly mobile large scale pure ad hoc wireless mesh networks
2009
In highly mobile pure ad-hoc wireless mesh networks, fast rerouting within low routing discovery delay is a mandatory requirement for routing algorithm to support interactive applications such as VoIP. Also, the communication overhead should be thwarted when networks grow to a large scale. We propose a Tree-Based Routing Algorithm - TBRA to facilitate such two goals. On one hand, TBRA has very low routing discovery delay due to its proactive property. On the other hand, TBRA performs more efficiently than other proactive protocols with respect to low communication overhead, which thanks to its short routing packet length, less numbers and smaller routing table size. Our modeling analysis an…
A flexible and tunable route discovery mechanism for on-demand protocols
2004
Mobile ad-hoc networks are characterized by multihop wireless links and absence of cellular infrastructure. For the last years, routing has been the area under most intensive research. In particular, on-demand routing protocols proposed are extremely attractive due to their low-overhead and efficiency. Currently, wireless ad-hoc networks lack multipath routing protocols. Multipath routing enables increased QoS support, load balancing and enhanced route stability. In this paper we present a new route discovery solution that increases the number of routes found, while reducing the routing overhead when compared to previous proposals. Simulation results show that the additional routing overhea…
Logic-Based Distributed Routing for NoCs
2008
The design of scalable and reliable interconnection networks for multicore chips (NoCs) introduces new design constraints like power consumption, area, and ultra low latencies. Although 2D meshes are usually proposed for NoCs, heterogeneous cores, manufacturing defects, hard failures, and chip virtualization may lead to irregular topologies. In this context, efficient routing becomes a challenge. Although switches can be easily configured to support most routing algorithms and topologies by using routing tables, this solution does not scale in terms of latency and area. We propose a new circuit that removes the need for using routing tables. The new mechanism, referred to as logic-based dis…
A multi-parametric evolution strategies algorithm for vehicle routing problems
2007
Vehicle routing problems are at the heart of most decision support systems for real-life distribution problems. In vehicle routing problem a set of routes must be determined at lowest total cost for a number of resources (i.e. fleet of vehicles) located at one or several points (e.g. depots, warehouses) in order to efficiently service a number of demand or supply points. In this paper an efficient evolution strategies algorithm is developed for both capacitated vehicle routing problem and for vehicle routing problem with time window constraints. The algorithm is based on a new multi-parametric mutation procedure that is applied within the 1 + 1 evolution strategies algorithm. Computational …
Cost-Efficient On-Chip Routing Implementations for CMP and MPSoC Systems
2011
[EN] The high-performance computing domain is enriching with the inclusion of networks-on-chip (NoCs) as a key component of many-core (CMPs or MPSoCs) architectures. NoCs face the communication scalability challenge while meeting tight power, area, and latency constraints. Designers must address new challenges that were not present before. Defective components, the enhancement of application-level parallelism, or power-aware techniques may break topology regularity, thus, efficient routing becomes a challenge. This paper presents universal logic-based distributed routing (uLBDR), an efficient logic-based mechanism that adapts to any irregular topology derived from 2-D meshes, instead of usi…
Power-constrained sensor selection and routing for cooperative detection in cognitive radios
2012
Given a spectrum-sensing network, a set of active nodes jointly aggregate sensed data at a preset frequency-band and simultaneously route this information to an arbitrarily chosen querying node through a power-constrained multi-hop path. Locally, each sensor node is assumed to be an energy-based detector. This work focuses on deriving algorithms that jointly optimize sensor selection and cooperative detection from which a power-efficient route to the querying node can be established, and then, a tree routing structure spanning the chosen nodes is constructed under a power budget constraint. Sensor information is sequentially aggregated along this optimized routing structure up to the queryi…
ECAR: an Energy/Channel Aware Routing Protocol For Cooperative Wireless Sensor Networks
2011
International audience; The proliferation of low power networks like Wireless Sensor Networks (WSN) rose up new challenges. Power conservation and channel quality become the most important parameters. Obviously, hop count based routing protocols are no more adapted to such networks having power limitations and channel problems. Several alternatives were suggested to cope with these constraints. In MAC layer for example, cooperative protocols were designed to enhance the channel use: the neighbor nodes help the source to retransmit its packets. However, if the path proposed by the routing protocol contains poor channels, the cooperative communications will not save all the packets. Therefore…